package com.sasac.common.core.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * @author X.H.Yang
 */
public class TreeID3Act {

//    天气  晴=2，阴=1，雨=0
//    风速，强= 1，弱=0；
//    湿度，高=1，正常=0；
//    温度，炎热=2，正常=1，寒冷=0。

    public static String[] createDataLable() {
        String lable[] = {"weather", " temper", "humidity", "wind"};
        return lable;
    }

    public static Object[][] createDataSet() {
        Object set[][] = {{2, 2, 1, 0, "no"},
                {2, 2, 1, 1, "no"},
                {1, 2, 1, 0, "yes"},
                {0, 1, 1, 0, "yes"},
                {0, 0, 0, 0, "yes"},
                {0, 0, 0, 1, "no"},
                {1, 0, 0, 1, "yes"},
                {2, 1, 1, 0, "no"},
                {2, 0, 0, 0, "yes"},
                {0, 1, 0, 0, "yes"},
                {2, 1, 0, 1, "yes"},
                {1, 1, 1, 1, "yes"},
                {1, 2, 0, 0, "yes"},
                {0, 1, 1, 1, "no"}};
        return set;
    }

    public static double calcShannonEnt(Object[][] dataSet) {
        double shannonEnt = 0.0;
        int numEntries = dataSet.length;
        HashMap<String, Integer> labelCounts = new HashMap<>();
        for (Object[] featVec : dataSet) {
            String currentLabel = (String) featVec[featVec.length - 1];
            if (labelCounts.get(currentLabel) == null) {
                labelCounts.put(currentLabel, 1);
            } else {
                int i = labelCounts.get(currentLabel);
                i++;
                labelCounts.put(currentLabel, i);
            }
        }
        for (Entry<String, Integer> entry : labelCounts.entrySet()) {
            double prob = (double) entry.getValue() / (double) numEntries;
            shannonEnt -= prob * (Math.log(prob) / Math.log(2.0d));
        }
        return shannonEnt;
    }

    public static ArrayList<Object[]> splitDataSet(Object dataSet[][], int axis, Object value) {
        ArrayList<Object[]> retDataSet = new ArrayList<>();
        for (Object[] featVec : dataSet) {
            Object subSet[] = null;
            if (featVec[axis].equals(value)) {
                subSet = new Object[dataSet[0].length - 1];
                if (axis == 0) {
                    System.arraycopy(featVec, 1, subSet, 0, subSet.length);
                } else {
                    System.arraycopy(featVec, 0, subSet, 0, axis);
                    System.arraycopy(featVec, axis + 1, subSet, axis, subSet.length - axis);
                }
                retDataSet.add(subSet);
            }
        }
        return retDataSet;
    }

    public static int chooseBestFeatureToSplit(Object dataSet[][]) {
        int numFeatures = dataSet[0].length - 1;
        double baseEntropy = calcShannonEnt(dataSet);
        double bestInfoGain = 0.0;
        int bestFeature = -1;
        for (int f = 0; f < numFeatures; f++) {
            HashSet<Object> uniqueVals = new HashSet<>();
            for (Object set[] : dataSet) {
                uniqueVals.add(set[f]);
            }
            double newEntropy = 0.0;
            for (Object obj : uniqueVals) {
                ArrayList<Object[]> subDataSet = splitDataSet(dataSet, f, obj);
                double prob = (double) subDataSet.size() / (double) dataSet.length;
                Object subSetArray[][] = new Object[subDataSet.size()][numFeatures];
                for (int i = 0; i < subSetArray.length; i++) {
                    System.arraycopy(subDataSet.get(i), 0, subSetArray[i], 0, numFeatures);
                }
                newEntropy += prob * calcShannonEnt(subSetArray);
            }
            double infoGain = baseEntropy - newEntropy;
            if (infoGain > bestInfoGain) {
                bestInfoGain = infoGain;
                bestFeature = f;
            }
        }
        return bestFeature;
    }

    public static String majorityCnt(String classList[]) {
        HashMap<String, Integer> classCount = new HashMap<>();
        for (String vote : classList) {
            if (!classCount.containsKey(vote)) {
                classCount.put(vote, 1);
            } else {
                int i = classCount.get(vote);
                i++;
                classCount.put(vote, i);
            }
        }
        LinkedHashMap<String, Integer> sortMap = sortMapByValues(classCount);
        return sortMap.entrySet().iterator().next().getKey();
    }

    private static Object createTree(Object dataSet[][], String labels[]) {
        //classList = [example[-1] for example in dataSet]
        ArrayList<String> classList = new ArrayList();
        for (Object set[] : dataSet) {
            classList.add((String) set[set.length - 1]);
        }
        if (ListCount(classList, classList.get(0)) == classList.size()) {
            return classList.get(0);
        }
        if (dataSet[0].length == 1) {
            return majorityCnt((String[]) classList.toArray());
        }
        int bestFeat = chooseBestFeatureToSplit(dataSet);
        String bestFeatLabel = labels[bestFeat];
        HashMap myTree = new HashMap<>();
        myTree.put(bestFeatLabel, new HashMap<>());
        String sublabels[] = new String[labels.length - 1];
        if (bestFeat == 0) {
            System.arraycopy(labels, 1, sublabels, 0, sublabels.length);
        } else {
            System.arraycopy(labels, 0, sublabels, 0, bestFeat);
            System.arraycopy(labels, bestFeat + 1, sublabels, bestFeat, sublabels.length - bestFeat);
        }
        HashSet<Object> uniqueVals = new HashSet<>();
        for (Object set[] : dataSet) {
            uniqueVals.add(set[bestFeat]);
        }
        for (Object value : uniqueVals) {
            ArrayList<Object[]> setlist = splitDataSet(dataSet, bestFeat, value);
            int j = 0;
            Object dataSetM[][] = new Object[setlist.size()][];
            for (Object set[] : setlist) {
                dataSetM[j] = set;
                j++;
            }
            Object tree = createTree(dataSetM, sublabels);
            HashMap subtree = (HashMap) myTree.get(bestFeatLabel);
            subtree.put(value, tree);
        }
        return myTree;
    }

    private static String classify(HashMap<Object, Object> inputTree, String featLabels[], Object[] testVec) {
        String firstStr = (String) inputTree.keySet().iterator().next();
        HashMap secondDict = (HashMap) inputTree.get(firstStr);
        int featIndex = 0;
        for (featIndex = 0; featIndex < featLabels.length; featIndex++) {
            if (featLabels[featIndex].equals(firstStr)) {
                break;
            }
        }
        Object key = testVec[featIndex];
        Object valueOfFeat = secondDict.get(key);
        String classLabel = "erro";
        if (valueOfFeat instanceof HashMap) {
            classLabel = classify((HashMap<Object, Object>) valueOfFeat, featLabels, testVec);
        } else {
            classLabel = (String) valueOfFeat;
        }
        return classLabel;
    }

    private static int ListCount(ArrayList<String> classList, String key) {
        int c = 0;
        for (String clazz : classList) {
            if (clazz.equals(key)) {
                c++;
            }
        }
        return c;
    }

    private static LinkedHashMap<String, Integer> sortMapByValues(Map<String, Integer> aMap) {

        Set<Entry<String, Integer>> mapEntries = aMap.entrySet();

        //System.out.println("Values and Keys before sorting ");
        //for (Entry<String, Integer> entry : mapEntries) {
        //System.out.println(entry.getValue() + " - " + entry.getKey());
        //}
        // used linked list to sort, because insertion of elements in linked list is faster than an array list.
        List<Entry<String, Integer>> aList = new LinkedList<Entry<String, Integer>>(mapEntries);

        // sorting the List
        Collections.sort(aList, new Comparator<Entry<String, Integer>>() {

            @Override
            public int compare(Entry<String, Integer> ele1, Entry<String, Integer> ele2) {

                return -(ele1.getValue().compareTo(ele2.getValue()));
            }
        });

        // Storing the list into Linked HashMap to preserve the order of insertion.
        LinkedHashMap<String, Integer> aMap2 = new LinkedHashMap<String, Integer>();
        for (Entry<String, Integer> entry : aList) {
            aMap2.put(entry.getKey(), entry.getValue());
        }
        return aMap2;
    }


    //    天气  晴=2，阴=1，雨=0
//    温度，炎热=2，正常=1，寒冷=0。
//    湿度，高=1，正常=0；
//    风速，强= 1，弱=0；
    public static void main(String[] args) throws Exception {
        Object Dataset[][] = createDataSet();
        Object tree = createTree(Dataset, new String[]{"weather", " temper", "humidity", "wind"});
        System.out.println(tree);
        String clazz = classify((HashMap<Object, Object>) tree, new String[]{"weather", " temper", "humidity", "wind"}, new Object[]{2, 1, 1, 0});
        System.out.println(clazz);
    }
}